package 滑动窗口;

import javafx.util.converter.ShortStringConverter;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/* 该题目还是滑动窗口， 先用hash1 来记录 words所有的单词频次
* hash2来比较，当前锁定的单词是否为hash1中出现过，也就是words中的单词，如果是 count++，如果不是略过
* 当right-left+1 （当前检索的单词长度）> words总单词长度时，出窗口，hash2[left]记数-1，并出，left+=len，将左指针移动到下一个单词
* 当 count （有效字符数） == m（words中总单词量）。记录left下标*/
public class 串联所有单词的子串 {

    public List<Integer> findSubstring(String s, String[] words)
    {
        List<Integer> ret = new ArrayList<Integer>();
        Map<String,Integer> hash1 = new HashMap<String,Integer>();  //保存字典中所有单词的频次
        for(String str : words) hash1.put(str,hash1.getOrDefault(str,0)+1);

        int len = words[0].length(),m = words.length;
        for(int i = 0; i<len ; i++) {

            Map<String, Integer> hash2 = new HashMap<String, Integer>();  //保存窗口内所有单词的频次
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {

                // 进窗口，维护
                String in  = s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;
                // 判断
                if(right-left+1 > len* m){
                    // 出窗口+维护 count
                    String  out = s.substring(left,left+len);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count --;
                    hash2.put(out,hash2.get(out)-1);
                    left+=len ;
                }
                // 更新结果
                if(count == m)  ret.add(left);
            }
        }
        return ret;


    }


    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> ret = new ArrayList<Integer>();
        Map<String,Integer>  hash1 = new HashMap<String,Integer>();
        for(String str : words) hash1.put(str,hash1.getOrDefault(str,0)+1);

        int len = words[0].length(),m = words.length;

        for(int i = 0 ;i<len ; i++){
            Map<String,Integer> hash2 = new HashMap<String,Integer>();

            for(int left = i,right = i ,count = 0 ; right+len<s.length();right+=len){

                String in = s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in)<= hash1.getOrDefault(in,0)) count++;

                if(right-left+1 > len*m){
                    String out = s.substring(left,left+len);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out)-1);
                    left +=len;
                }

                if(count == m){
                    ret.add(left);
                }
            }
        }
        return ret;
    }

}



